// #include <vector>
// using namespace std;

// class Solution {
// public:
//     vector<int> sortArray(vector<int>& nums) {
//         if (nums.empty()) return {};
//         vector<int> arr = nums; // 创建副本用于排序
//         mergeSort(arr, 0, arr.size() - 1); 
//         return arr;
//     }
    
//     void mergeSort(vector<int>& nums, int l, int r) {
//         if (l >= r) return;
        
//         int mid = (l + r) / 2;
//         // 递归划分
//         mergeSort(nums, l, mid);
//         mergeSort(nums, mid + 1, r);
        
//         // 合并两个有序数组
//         merge(nums, l, mid, r);
//     }
    
//     void merge(vector<int>& nums, int l, int mid, int r) {
//         // 创建临时数组
//         vector<int> temp(r - l + 1);
//         int left = l;
//         int right = mid + 1;
//         int i = 0;
        
//         // 合并两个有序部分,为什么是有序的，那2 1 5 3 举个例子把,分治到最后肯定就只有两个元素了 比如2 1此时 排序变成 1 2 同时右边也是变成 3 5,这样左右两边肯定都是有序的， 然后在排序这个 1 2 3 5那么返回到
//上一层的时候它可能也是左右的某一个部分，另一个部分肯定也是排好序的
//         while (left <= mid && right <= r) {
//             if (nums[left] <= nums[right]) {
//                 temp[i++] = nums[left++];
//             } else {
//                 temp[i++] = nums[right++];
//             }
//         }
        
//         // 复制剩余元素
//         while (left <= mid) {
//             temp[i++] = nums[left++];
//         }
//         while (right <= r) {
//             temp[i++] = nums[right++];
//         }
        
//         // 将临时数组复制回原数组
//         for (int j = 0; j < temp.size(); j++) {
//             nums[l + j] = temp[j];
//         }
//     }
// };


// class Solution {
// public:
//     int reversePairs(vector<int>& record) {
//         //先搞懂一个问题
//         //举一个例子 7 5 4 6
//         //以这个例子为例子，假设左半边为7 5 右半边为 4 6
//         //我们可以先求左半边的逆序对，然后再求右边的逆序对，（这一步之前，我们可以先把左边排序，然后再把右边排序，这样并不影响我们找下一步找逆序对）最后在求一个数在左边，一个数在右边的逆序对。然后他们三个值相加
//         //为什么要排序 我们排序完是这样的 5 7 4 6
//         我们第一次选左边的5，右边的4，我们知道5 4为一个逆序对，然后
//         5右边的，而且属于左半部分的一定大于4也就一定构成逆序对，所以这样就少比对了，时间复杂度就会降低了
//     }
// };
// https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/x
// class Solution {
// public:
//     int reversePairs(vector<int>& record) {
//         if (record.empty())
//             return {};
//         return mergeSort(record, 0, record.size() - 1);;
//     }
//     int mergeSort(vector<int>& nums, int l, int r) {
//         if (l >= r)
//             return 0;
//         int ret = 0; int mid = (l + r) / 2;
//         // 递归划分
//         ret += mergeSort(nums, l, mid);
//         ret += mergeSort(nums, mid + 1, r);

//         // 合并两个有序数组
//         // 创建临时数组
//         vector<int> temp(r - l + 1);
//         int left = l;
//         int right = mid + 1;
//         int i = 0;

//         // 合并两个有序部分
//         while (left <= mid && right <= r) {
//             if (nums[left] <= nums[right]) {
//                 temp[i++] = nums[left++];
//             } else {
//                 ret += mid - left + 1;
//                 temp[i++] = nums[right++];
//             }
//         }

//         // 复制剩余元素
//         while (left <= mid) {
//             temp[i++] = nums[left++];
//         }
//         while (right <= r) {   
//             temp[i++] = nums[right++];
//         }

//         // 将临时数组复制回原数组
//         for (int j = 0; j < temp.size(); j++) {
//             nums[l + j] = temp[j];
//         }
//         return ret;
//     }
// };